Check if N and its double exist

Time: O(N); Space: O(N); easy

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that : * i != j * 0 <= i, j < len(arr) * arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]

Output: True

Explanation:

  • N = 10 is the double of M = 5, that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]

Output: True

Explanation:

  • N = 14 is the double of M = 7, that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]

Output: False

Explanation:

  • In this case does not exist N and M, such that N = 2 * M.

Notes:

  • 2 <= len(arr) <= 500

  • -10^3 <= arr[i] <= 10^3

Hints:

  1. Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].

  2. On each step of the loop check if we have seen the element 2 * arr[i] so far or arr[i] / 2 was seen if arr[i] % 2 == 0.

[5]:

class Solution1(object):
    def checkIfExist(self, arr):
        """
        :type arr: List[int]
        :rtype: bool
        """
        lookup = set()

        for x in arr:
            if 2*x in lookup or (x%2 == 0 and x//2 in lookup):
                return True
            lookup.add(x)
        return False

[6]:

s = Solution1()

arr = [10,2,5,3]
assert s.checkIfExist(arr) == True

arr = [7,1,14,11]
assert s.checkIfExist(arr) == True

arr = [3,1,7,11]
assert s.checkIfExist(arr) == False